# coding:utf-8
# author:fxh

#打印尺子
"""
1
1 2 1
1 2 1 3 1 2 1
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1
递归公式：f(n-1)+f(n)+f(n-1)
"""
#时间复杂度：O(2^N)
def rule_bad(n):
    assert (n>=0)
    if n == 1:
        return "1"
    return rule_bad(n-1) + " " + str(n)+" " +rule_bad(n-1)

#优化：利用变量存储起来使用,节约内存
#时间复杂度：O(N)
def rule(n):
    assert (n>=0)
    if n == 1:
        return "1"
    #利用 t 变量存储 n-1情况下的值
    t = rule(n-1)
    return t + " " + str(n) + " " + t

if __name__ == '__main__':
    print(rule_bad(2))
    print(rule_bad(3))

    print(rule(9))
    print(rule(10))

